Un acertijo: tienes 5 cajas cerradas puestas en fila y en una de ellas hay un gato, al cual tienes que encontrar. Puedes elegir una caja y abrirla. Si el gato no se encuentra en esa caja, la cierras. Al día siguiente, el gato se habrá movido a una caja adyacente a la que se encontraba el día anterior. Con esta información, has de dar un método para siempre encontrar al gato en un número finito de días.
Puedes usar la siguiente interfaz para jugar (está explicada al final de la página), aunque creo que es más educativo que la primera vez que lo resuelvas no la utilices.
Una vez resuelto, podemos pensar en una posible generalización de este juego: la adyacencia de las cajas viene dada por un grafo cualquiera. Vemos rápidamente que no siempre podemos encontrar al gato con estas reglas en un grafo el que sea. Por ejemplo, en un ciclo abramos la caja que abramos, siempre quedará una caja adyacente desde la que “propagarse el gato”. Sin embargo, podemos ganar si abrimos 2 cajas a cada paso. ¿Dado el grafo \(G\), cuál es el menor número de cajas a abrir cada día que nos asegure poder encontrar el gato? Sea \(s(G)\) dicho número. Adjunto las pocas cotas que conozco (la 3 y la 4 son un caso particular de la 2), cuya demostración se deja como ejercicio:
\(H \subseteq G \implies s(H) \leq s(G)\)
\(\max_{H \leq G} \delta(H) \leq s(G)\)
\(\delta(G) \leq s(G)\)
\(\omega(G) - 1 \leq s(G)\)
\(s(G) \leq |V(G)| - \alpha(G)\)
\(s(G \land H) \leq \min \{s(G) + |H|, s(H) + |G| \}\)
En este enlace se discute en qué grafos se puede ganar abriendo solo una caja a cada vez. En este otro enlace, la generalización a grids (supongo que la traducción es cuadrícula).
Le doy las gracias a Nacho por contarme este acertijo y a Luis por ayudarme a discutir esta generalización sin sentido y a sacar las cotas.
Algunos autores consideran una ardilla en vez de un gato. Gracias a Rodrigo por hablarme acerca de esta variante del problema.
¡Gracias también a ti por leer! Si tienes alguna idea sobre este problema/juego, no dudes en contactarme.
Path 4 Path 5 Path 6 Path 7 Path 8
Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8
Grid 3 Grid 4 Grid 5 Grid 6 Grid 7 Grid 8
Petersen Sobre Estrella IraIACOCG
Como me huelo que se me va a olvidar, he aquí cómo funciona la interfaz simuladora de gatos/ardillas en cajas de arriba del todo. Tiene dos modos: Editar y Jugar. Para cambiar entre estos dos, hacer click sobre el correspondiente botón.
Jugar: haciendo click sobre una caja, esta se abre revelando que no hay gato. Al abrir todas las cajas disponibles para el día, cada gato potencial se propaga a todas sus cajas adyacentes. El botón “Reiniciar” pone un gato potencial en cada caja (reinicia el juego).
Editar: al hacer click sobre un lugar donde no hay cajas, se crea un nuevo vértice/caja. Haciendo click sobre una caja y luego sobre otra distinta, se crea una arista. “Cajas por día” es el párametro que controla cuántas cajas se pueden abrir cada día. Al hacer click sobre el botón “Borrar vértice” y luego sobre un vértice/caja, este/esta se elimina junto con todas sus aristas. “Borrar grafo” elimina todos los vértices y aristas.